import java.util.*;

class Solution1 {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] len = new int[n];
        int[] count = new int[n];
        for (int i = 0; i < n; i++) {
            len[i] = count[i] = 1;
        }

        int retlen = 1, retcount = 1;
        for (int i = 1; i < n; i++) {
            for(int j = 0; j<i;j++) {
                if(nums[j] < nums[i]) {
                    if(len[j] + 1 == len[i]) {
                        count[i] += count[j];
                    }else if(len[j] + 1 > len[i]) {
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    }
                }
            }

            if(retlen == len[i]) {
                retcount += count[i];
            }else if(retlen < len[i]) {
                retlen = len[i];
                retcount = count[i];
            }
        }
        return retcount;
    }
}


class Solution2 {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        int n = pairs.length;
        if( n== 1) return 1;
        int[] dp = new int[n];
        for(int i = 0; i<n; i++) {
            dp[i] = 1;
        }

        int ret = Integer.MIN_VALUE;
        for(int i = 1; i<n; i++) {
            for(int j = 0; j<i; j++) {
                if(pairs[j][1] < pairs[i][0]) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            ret = Math.max(ret,dp[i]);
        }
        return ret;
    }
}

class Solution3 {
    public int longestSubsequence(int[] arr, int difference) {
        int n = arr.length;
        HashMap<Integer,Integer> map = new HashMap<>();
        int ret = Integer.MIN_VALUE;
        map.put(arr[0],1);

        for(int i= 1;i<n; i++) {
            int x = arr[i] - difference;
            if(map.containsKey(x)) {
                map.put(arr[i], Math.max(map.getOrDefault(arr[i],1), map.get(x) + 1));
            }else {
                map.put(arr[i],1);
            }
            ret = Math.max(ret,map.get(arr[i]));
        }

        return ret;
    }
}

class Solution4 {
    public int longestSubsequence(int[] arr, int difference) {
        int n = arr.length;
        HashMap<Integer,Integer> map = new HashMap<>();
        int ret = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            map.put(arr[i],1);
        }

        for(int i= 1;i<n; i++) {
            int x = arr[i] - difference;
            if(map.containsKey(x)) {
                map.put(arr[i], Math.max(map.getOrDefault(arr[i],1), map.get(x) + 1));
            }
            System.out.print(map.get(arr[i]) + " ");
            ret = Math.max(ret,map.get(arr[i]));
        }

        return ret;
    }
}

class ListNode {
     int val;
     ListNode next;
    ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

class Solution5 {
    public int[] reverseBookList(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ListNode cur = head;
        while(cur != null) {
            stack.push(cur.val);
            cur = cur.next;
        }

        int n = stack.size();
        int[] ret = new int[n];
        int index = 0;
        while(!stack.isEmpty()) {
            ret[index++] = stack.pop();
        }
        return ret;
    }
}

class Solution6 {
    public ListNode removeDuplicateNodes(ListNode head) {
        Set<Integer> set = new HashSet<>();
        ListNode newHead = new ListNode();
        newHead.next = head;
        ListNode prev = newHead, cur = head;
        while(cur!=null) {
            if(!set.contains(cur.val)) {
                set.add(cur.val);
                prev = cur;
                cur = cur.next;
            }else {
                prev.next = cur.next;
                cur = cur.next;
            }
        }
        return newHead.next;
    }
}

class Solution7 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head3 = new ListNode();
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        ListNode cur3 = head3;

        int t = 0;
        while(cur1!=null || cur2!=null) {
            int x = (cur1 == null ? 0 : cur1.val) + (cur2 == null ? 0 : cur2.val) + t;
            ListNode node = new ListNode(x%10);
            t = x/10;
            System.out.print(node.val + " ");
            cur3.next = node;
            cur3 = cur3.next;
            if(cur1!=null) {
                cur1 = cur1.next;
            }
            if(cur2!=null) {
                cur2 = cur2.next;
            }
        }
        if(t != 0) {
            ListNode node = new ListNode(t);
            cur3.next = node;
        }

        return head3.next;
    }
}


class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode newHead = new ListNode();
        newHead.next = head;
        HashMap<Integer, ListNode> hashMap = new HashMap<>();
        int sum = 0;
        ListNode cur = head;
        while(cur != null) {
            sum += cur.val;
            hashMap.put(sum, cur);
            cur = cur.next;
        }

        cur = newHead.next;
        sum = 0;
        while(cur != null) {
            sum += cur.val;
            cur.next = hashMap.get(sum).next;
            cur = cur.next;
        }

        return newHead.next;
    }
}

public class Test {
}
